perm filename LOCUS1[0,BGB]1 blob
sn#116847 filedate 1974-08-30 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 {≤G⊂CαLOCUS SOLVING.λ30P101I425,0JCFA} SECTION 9.
C00005 00003 ⊂9.1 An Eight Parameter Camera Model.⊃
C00007 00004
C00010 00005 ~Camera Resolution~. The focal ratio description allows one
C00013 00006 {QW0,1260,0,1900I200,0}⊂9.2 Camera Locus Solving: One View of Three Points⊃
C00016 00007 {W0,750,100,1900λ25JUFA}
C00021 00008
C00024 00009
C00028 00010
C00031 ENDMK
C⊗;
{≤G;⊂C;αLOCUS SOLVING.;λ30;P101;I425,0;JCFA} SECTION 9.
{JCFD} CAMERA AND FEATURE LOCUS SOLVING.
{λ10;W250;JAFA}
9.0 Introduction to Locus Solving.
9.1 An Eight Parameter Camera Model.
9.2 Camera Locus Solving: One View of Three Points.
9.3 Object Locus Solving: Silhouette Cone Intersection.
9.4 Sun Locus Solving: A Simple Solar Ephemeris.
9.5 Related and Future Locus Solving Work.
{λ30;W0;I950,0;JUFA}
⊂9.0 Introduction to Locus Solving.⊃
There are three kinds of locus solving problems in computer
vision: camera locus solving, feature locus solving and sun locus
solving. Camera solving is routinely attempted in two ways: using one
image the 2-D image loci of a set of already known 3-D world loci
(perhaps points on a calibration object) are measured and a camera
model is computed; or using two or more images a set of corresponding
landmark feature points are found among the images and the whole
system is solved relative to itself. After the camera positions are
known, the location and extent of the objects composing the scene can
be found using parallax (motion parallax and stereo parallax).
Parallax is the principal means of depth perception and is the
alchemist for converting 2-D images into 3-D models. After the camera
and object positions are known to some accuracy, the nature and
location of light sources might potentially be deduced from the
shines and shadows in the images. However, in outdoor situations the
primary light source is the sun, whose position in the sky can be
computed from the time, date and latitude by means of a
simple solar ephemeris routine.{Q}
⊂9.1 An Eight Parameter Camera Model.⊃
In GEOMED and CRE the basic camera model is specified by
eight parameters. There are three parameters for the lens center
location of the camera: CX, CY, CZ; three parameters for the
orientation: WX, WY, WZ; and two parameters for the projection
ratios: the aspect ratio, AR; and the focal ratio, FR.
The location is given in world coordinates and the orientation is
specified by a rotation vector whose direction
gives an axis and whose magnitude gives rotation which when applied to
a set of three axes unit vectors yields a set of unit vectors that
determines the camera's coordinate system. By convention the principal
ray of the camera is parallel to the Z axis unit vector and is
negatively directed. The camera raster is alligned such that the rows
(vidicon scan lines) are parallel to the X unit vector and the
columns are parallel to the Y unit vector.
The aspect ratio, AR, is the ratio of width, PDX, to height,
PDY, of a single vidicon sample point called a pixel: AR = PDX/PDY.
The focal ratio, FR, is the ratio of the focal plane distance to the
height of a single pixel: FR = FOCAL/PDY. The typical value of the
aspect ratio is about one, and the typical value of the focal ratio
runs from 300 to 3000.
The actual physical size of the digital raster of a
television vidicon is on the order of 12 millimeters wide by 8
millimeters high with approximately 512 lines of potentially 512
pixels per line. However, a standard television scans its raster in
two phases (odd rows in one phase, even rows in the next) so that a
one-phase pixel is approximately 40 microns by 40 microns (rather
than 20 by 20). By contrast, the cones and rods in a human eye are 1
and 2 microns in diameter respectively.
The aspect ratio and the focal ratio can be measured
individually using a spherical calibration object. I have used
plastic toy balls and billiard balls, billiard ball radius
RBB=2.125". The perspective projection of a sphere is an ellipse and
the ratio of the apparent width to height of the ellipse of a sphere
that nearly fills the viewing screen is the aspect ratio. To measure
the focal ratio, mount the sphere on a stick and measure its apparent
radii (r1 and r2) at two positions that are approximately along the
camera's principal axis a measured distance, DZ, apart. Then then
the focal ratio FR = DZ*r1*r2/(R*(r1-r2)) which can be thought of as
the FOCAL plane distance in pixels. The beauty of this is that a
naive measuring method yields results as good as measurements
obtained by more elaborate methods such as principal axis relaxation
of a camera model in numerous variables (Sobel 70) and Pingle
unpublished.
~Camera Resolution~. The focal ratio description allows one
to have a firm numerical intuition of camera's spatial resolution in
the object space. The smallest distance interval, DELTA, a camera can
measure at a given range, RNG, is merely the ratio of range to FR:
DELTA=RNG/FR. The arctan of the reciprocal of the focal ratio
ARCTAN(1/FR) is the angle subtended by a single pixel.
~Lens Center Irrelevancy Theorem~. The actual location of the
principal axis of the lens in the image plane is irrelevant because
the effect of deviation from the true center is equivalent to
rotating the camera Many camera modelists worry needlessly about the
exact location of the camera lens center; the angular error, ANGERR,
of a pixel X units from the center of the image of a camera modeled
with a lens center that is wrong in the X direction by Q pixels is
given by the following expression:
{JC} ANGERR = ARCTAN(X/FR) - ARCTAN((X+Q)/FR) - ARCTAN(Q/FR)
\Which for the physical parameters of the television hardware at
Stanford in 1974; means that the lens center can be allowed to wander
by tens of pixels from its true position without causing a pixel of
error at the edge of the image, (allowing that one camera model is
alligned on the same feature by rotation as the camera that defines a
good lens center).
{Q;W0,1260,0,1900;I200,0;}⊂9.2 Camera Locus Solving: One View of Three Points⊃
{FC} - The Iron Triangle Camera Solving Method.{FA;λ30;}
A mobile robot having only visual perception must determine
where it is going by what it sees. Specifically, the position of the
robot is found relative to the position of the lens center of its
camera. The following algorithm is a geometric method for computing
the locus of a camera's lens center from three landmark points.
{I∂500,0;}
Consider four non-coplanar points A, B, C and L. Let L be
the unknown camera's lens center, also called the camera
locus. Let A, B and C be the landmark points whose loci either
are given on a map or are found by stereo from two already known
viewing positions. Assuming for the moment an ideal camera which can
see all 4π steradians at once, the camera can measure the angles
formed by the rays from the camera locus to the landmark points. Let
these angles be called ≤a≥, ≤b≥ and ≤g≥ where ≤a≥ is the angle BLC,
≤b≥ is the angle ALC and ≤g≥ is the angle ALB. The camera also
measures whether the landmarks appear to be in clockwise or counter
clockwise order as seen from L. If the landmarks are counterclockwise
then B is swaped with C and ≤b≥ with ≤g≥. A mechanical analog of the
problem would be to position a rigid triangular piece of sheet metal
between the legs of a tripod so that its corners touch each leg. The
metal triangle is the same size as the triangle ABC and the legs of
the tripod are rigidly held forming the angles ≤a≥, ≤b≥ and ≤g≥. The
algorithm was developed by thinking in terms of this analogy.
{L-620,300;λ15;}FIGURE 9.1
The Iron Triangle and Tripod.
{L100,130;H3;X0.8;*IRONT.PLT;FD;
L100,130;I∂80,∂-280;}A{
L100,130;I∂-225,∂-130;}B{
L100,130;I∂270,∂-110;}C{
L100,130;I∂0,∂410;}L{
W0,1260,100,1800;FA;Q;λ10;}
{W0,750,100,1900;λ25;JUFA}
\In order to put the iron triangle
into the tripod, the edge BC is first placed
between the tripod legs of angle ≤a≥. Let
a be the length of BC, likewise b and c
are the lengths of AC and AB.
\Restricting attention to the plane LBC,
consider the locus of points L' arrived at
by sliding the tripod and maintaining
contacts at B and C.
\Remembering that in a circle, a chord
subtends equal angles at all points of each
arc on either side of the chord; it can be seen
that the set of possible L' points lie
on a circular arc. Let this arc be called L's arc, which is part of L's
circle.
\Also in a circle the angle at the center
is double the angle at the
circumference, when the rays forming the
angles meet the circumference in the
same two points.
\And the perpendicular bisector of a
chord passes thru the center of the
chord's circle bisecting the central
angle. Let S be the distance between the
center of the circle and the chord BC.
So by trigonometric definitions:
{JC} R = a / 2sin(≤a≥)
{JC} S = R cos(≤a≥)
{H3;
L560,700;C5;I∂10,∂20;}L{I∂0,∂-120;}≤a≥{L560-320,690;}a{
L560,700,560-350,700+94;
L560,700,560-350,700-94;
L560,700;C50,165*π/180,30*π/180;
L400-138,700+80;C5;I∂-10,∂-5;}B{
L400-138,700-80;C5;I∂30,∂-5;}C{
L400-138,700+80,400-138,700-80;
L560,400;C5;I∂10,∂20;}L{I∂0,∂-120;}≤a≥{L560-320,390;}a{
L560,400,560-350,400+94;
L560,400,560-350,400-94;
L560,400;C50,165*π/180,30*π/180;
L400-138,400+80;C5;I∂-10,∂-5;}B{
L400-138,400-80;C5;I∂30,∂-5;}C{
L400-138,400+80,400-138,400-80;
L502,522;C5;I∂0,∂10;}L'{
L502-70,522-35;}≤a≥{
L502,522;C50,190*π/180,30*π/180;
L502,522,502-345,522-60;
L502,522,502-268,522-225;
L560,100;C5;I∂10,∂20;}L{I∂0,∂-120;}≤a≥{L560-315,90;}a{
L560,100,560-350,100+94;
L560,100,560-350,100-94;
L560,100;C50,165*π/180,30*π/180;
L400-138,100+80;C5;I∂-10,∂-10;}B{
L400-138,100-80;C5;I∂30,∂-10;}C{
L400-138,100+80,400-138,100-80;
L502,222;C5;I∂0,∂10;}L'{
L502-70,222-35;}≤a≥{
L502,222;C50,190*π/180,30*π/180;
L502,222,502-345,222-60;
L502,222,502-268,222-225;
L400,100;C160;
L400,-300;C160;C5;
C50,150*π/180,60*π/180;I∂10,∂-90;}2≤a≥{
L400,-300,400-138,-300+80;
L400,-300,400-138,-300-80;
L560,-300;C5;I∂10,∂20;}L{I∂0,∂-120;}≤a≥{L560-315,-310;}a{
L560,-300,560-350,-300+94;
L560,-300,560-350,-300-94;
L560,-300;C50,165*π/180,30*π/180;
L400-138,-300+80;C5;I∂-10,∂-10;}B{
L400-138,-300-80;C5;I∂30,∂-10;}C{
L400-138,-300+80,400-138,-300-80;
L400,-700;C160,-150*π/180,300*π/180;C5;
L400-80,-700-30;}S{
L400-80,-700+50;}R{
L400-190,-700+25;}a/2{
L400,-700;
C50,150*π/180,30*π/180;I∂-10,∂-75;}≤a≥{
L400-138,-700+80;C5;I∂-10,∂-10;}B{
L400-138,-700-80;C5;I∂30,∂-10;}C{
L400-138,-700-80,400-138,-700+80,400,-700;
L400-138,-700,400+160,-700;
W0,1260,100,1800;
I120,680;FA}FIGURE 9.2 - FIVE IRON TRIANGLE DIAGRAMS.{
λ30;JUFAQ}
The position of L on its arc in the plane BLC can be
expressed in terms of one parametric variable omega ≤w≥, where ≤w≥
is the counter clockwise angular displacement of L from the
perpendicular bisector such that for ≤w≥=π-≤a≥, L is at B and for
≤w≥=≤a≥-π, L is at C. By spinning the iron triangle about the axis BC,
the vertex A sweeps a circle. Let H be the radius of A's circle and
let D be the directed distance between the center of A's circle and
the midpoint of BC. By Trigonometric relations on the triangle ABC:{
JA;λ10;T200;}
COS(ACB) = (a↑2 + b↑2 - c↑2)/2ab
SIN(ACB) = SQRT(1 - COS(C)↑2)
H = b SIN(ACB)
D = b COS(ACB) - a/2{JUFA;λ30;T-1;}
Now consider the third leg of the tripod which forms the
angles ≤b≥ and ≤g≥. The third leg intersects the BLC plane at point
L and extends into the appropriate halfspace so that the landmark
points appear to be in clockwise order as seen from L. Let A' be the
third leg's point of intersection with the plane containing A's
circle. Let the distance between the point A' and the center of A's
circle less the radius H of A's circle be called "The Gap". The gap's
value is negative if A' falls within A's circle. By constructing an
expression for the value of the Gap as a function of the parametric
variable ≤w≥, a root solving routine can find the ≤w≥ for which the
gap is zero thus determining the orientation of the triangle with
respect to the tripod and in turn the locus of the point L in space.
Using vector geometry, place an origin at the midpoint of BC,
establish the unit y-vector j pointing towards the vertex B, let the
plane BCL be the x-y plane and orient the unit x-vector i pointing
into L's halfplane. For right handedness, set the unit z-vector k to
i cross j. In the newly defined coordinates points B, C, and L become
the vectors:{JA;W200;λ10;T300;}
B = (-s, +a/2, 0);
C = (-s, -a/2, 0)
L = (R cos(w), R sin(w), 0)
Introducing two unknowns xx and zz the locus of point A' as a vector is:
A' = (xx, D, zz)
{Q}
The vectors corresponding to the legs of the tripod are:
LB = B - L = (-s-Rcos(w), +a/2-Rsin(w), 0)
LC = C - L = (-s-Rcos(w), -a/2-Rsin(w), 0)
LA = A'- L = (xx-Rcos(w), D-Rsin(w), zz)
Since the third leg forms the angles ≤b≥ and ≤g≥:
LA . LC = |LA| |LC| cos(≤b≥)
LA . LB = |LA| |LB| cos(≤g≥)
Solving each equation for |LA| yields:
|LA| = (LA . LC)/|LC|cos(≤b≥) = (LA . LB)/|LB|cos(≤g≥)
Multiplying by |LB| |LC| cos (≤b≥) cos (≤g≥) gives:
(LA . LC)|LB| cos(≤g≥) = (LA . LB)|LC| cos(≤b≥)
Expressing the vector quantites in terms of their components:
|LB| = sqrt((-S-Rcos(w))↑2 + (+a/2-Rsin(w))↑2)
|LC| = sqrt((-S-Rcos(w))↑2 + (-a/2-Rsin(w))↑2)
LA . LC = (xx-Rcos(w))(-s-Rcos(w)) + (D-Rsin(w))(-a/2-Rsin(w))
LA . LC = (xx-Rcos(w))(-s-Rcos(w)) + (D-Rsin(w))(+a/2-Rsin(w))
Substituting:
((xx-Rcos(w))(-s-Rcos(w)) + (D-Rsin(w))(-a/2-Rsin(w))) |LB|cos(≤g≥)
= ((xx-Rcos(w))(-s-Rcos(w)) + (D-Rsin(w))(+a/2-Rsin(w))) |LC|cos(≤b≥)
The previous equation is linear in xx, so solving for xx:
xx = P/Q + Rcos(w)
where
P = (-s-Rcos(w))(|LB|cos(≤g≥) - |LC|cos(≤b≥))
Q = (D-Rsin(w))((+a/2-Rsin(w))|LC|cos(≤b≥)
- (-a/2-Rsin(w))|LB|cos(≤g≥))
The unknown zz can be found from the definition of |LA|
|LA| = sqrt( (xx-Rcos(w))↑2 + (D-Rsin(w))↑2 + zz↑2)
so zz = sqrt( |LA|↑2 - (P/Q)↑2 - (D-Rsin(w))↑2)
and since:
|LA| = (LA . LC) / |LC|cos(≤b≥)
The negative values of zz are precluded by the clockwise ordering
of the landmark points. Thus the expression for the Gap can be formed:
GAP = sqrt( (XX+S)↑2 + zz↑2 ) - H
{W0;JUFA;λ30;T-1;}
As mentioned above, when the gap is zero the problem is solved
since the locus of A' then must be on A's circle, so the triangle
touches the third leg. The gap function looks like a cubic on its
interval [≤a≥-π,π-≤a≥] which almost always has just one zero crossing.
Having found the locus of L in the specially defined
coordinate system all that remains to do is to solve for the
components of L in the coordinate system that A, B and C were given.
This can be done by considering three vector expressions which are
not dependent on the frame of reference and do not have second order
L terms, namely: (CA dot CL); (CB dot CL); and ((CA x CB) dot CL).
Let the locus of L in the given frame of reference be (X,Y,Z) and let
the components of the points A, B and C be (XA,YA,ZA), (XB,YB,ZB)
and (XC,YC,ZC) respectively. Listing all four points in both frames
of reference:{λ10;T200;I∂-15,0;JA}
A = (xx, D, zz) = (XA, YA, ZA)
B = (-s, +a/2, 0) = (XB, YA, ZA)
C = (-s, -a/2, 0) = (XC, YC, ZC)
L = (Rcos(w),Rsin(w),0) = ( X, Y, Z)
Evaluating the vector expressions which are invariant:
CA = A - C = (XA-XC. YA-YC, ZA-ZC)
CB = B - C = (0, a, 0) = (XB-XC, YB-YC, ZB-ZC)
CL = L - C = (Rcos(w)+s,Rsin(w)+a/2,0) = ( X-XC, Y-YC, Z-ZC)
The dot products are:
CA . CL = (xx+S)(Rcos(w)+s)+(D+a/2)(Rsin(w)+A/2)
= (XA-XC)(X-XC) + (YA-YC)(Y-YC) + (ZA-ZC)(Z-ZC)
CB . CL = a(Rsin(w) + a/2)
= (XB-XC)(X-XC) + (YB-YC)(Y-YC) + (ZB-ZC)(Z-ZC)
The cross product is:
(CA x CB) . CL = -a zz(Rcos(w) + s)
= ((YA-YC)(ZB-ZC) - (ZA-ZC)(YB-YC)) (X-XC)
- ((XA-XC)(ZB-ZC) - (ZA-ZC)(XB-XC)) (Y-YC)
+ ((XA-XC)(YB-YC) - (YA-YC)(XB-XC)) (Z-ZC)
{JUFA;λ30;T-1;}
The last three equations are linear equations in the three
unknowns X, Y and Z which are readily isolated by Cramer's Rule. The
whole method has been implement in auxiliary programs LS1V3P and
QBALL which calibrate a camera with respect to a turntable for the
sake of the silhouette cone intersection demonstration in Section 9.3.